601A - The Two Routes - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int bfs(vector<int>adj[],int n){
  vector<int>vis(n+1,0);
  queue<int>q;
  q.push(1);
  vis[1]=1;
  int dis=0;
  while(!q.empty()){
    int size=q.size();
    while(size--){
      int node=q.front();
      q.pop();
      if(node==n) return dis;
      for(auto i:adj[node]){
        if(!vis[i]){
          vis[i]=1;
          q.push(i);
        }
      }
    }
    dis++;
  }
  return -1;
}

int main(){
  int n,m;
  cin>>n>>m;
  vector<int>adj1[n+1];
  map<pair<int,int>,int>edge;
  int flag=0;
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    if((u==1 && v==n) || (u==n && v==1)) flag=1;
    edge[{u,v}]++,edge[{v,u}]++;
    adj1[u].push_back(v);
    adj1[v].push_back(u);
  }
  if(!flag) cout<<bfs(adj1,n)<<"\n";
  else{
    vector<int>adj2[n+1];
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        if(edge.find({i,j})==edge.end()){
          adj2[i].push_back(j);
          adj2[j].push_back(i);
        }
      }
    }
    cout<<bfs(adj2,n)<<"\n";
  }
}